Although, the Hamiltonicity of solid grid graphs are polynomial-timedecidable, the complexity of the longest cycle problem in these graphs is stillopen. In this paper, by presenting a linear-time constant-factor approximationalgorithm, we show that the longest cycle problem in solid grid graphs is inAPX. More precisely, our algorithm finds a cycle of length at least$\frac{2n}{3}+1$ in 2-connected $n$-node solid grid graphs. Keywords: Longest cycle, Hamiltonian cycle, Approximation algorithm, Solidgrid graph.
展开▼
